//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 
//
// 你可以按 任何顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
//
// 示例 2： 
//
// 
//输入：n = 1, k = 1
//输出：[[1]] 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 1 <= k <= n 
// 
// Related Topics 回溯 👍 1073 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * [P77]_组合
 *
 * @author cjl
 * @date 2022-08-05 18:28:13
 */
public class P77_Combinations {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P77_Combinations().new Solution();
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<Integer> currList = new ArrayList<>();
            List<List<Integer>> resList = new ArrayList<>();
            combine(n, k, 1, currList, resList);
            return resList;
        }

        /**
         * 回溯法
         * @param n
         * @param k
         * @param currList
         * @param resList
         */
        public void combine(int n, int k, int curr, List<Integer> currList, List<List<Integer>> resList) {
            if (currList.size() == k) {
                resList.add(new ArrayList<>(currList));
                return;
            }
            if (curr > n) {
                return;
            }
            //不使用当前数据
            combine(n, k, curr + 1, currList, resList);
            //使用当前数据
            currList.add(curr);
            combine(n, k, curr + 1, currList, resList);
            currList.remove(currList.size() -1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}